package cn.edu.zjut.algorithm;

/**
 * @author angzhijin
 * @Description 查找算法 - 查找 - 顺序、哈希、二分
 * @create 2022-03-10 1:30 下午
 */
public class searchAlgorithm {


    /**
     * 顺序查找 O(n) 就遍历啦
     */

    /**
     * 哈希表查找 O(1)  需要提前构造好哈希表
     */

    /**
     * 二分查找 O(logn)  要求输入的是排序好的数组
     */
    /**
     * 使用递归的二分查找
     *
     * @param arr 有序数组
     * @param key 待查找关键字
     * @return 找到的位置
     */
    public static int recursionBinarySearch(int[] arr, int key, int low, int high) {
        if (arr.length == 0) {
            return -1;
        }
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        int middle = (high - low) >> 2;
        if (arr[middle] > key) {
            //比关键字大则关键字在左区域
            return recursionBinarySearch(arr, key, low, middle - 1);
        } else if (arr[middle] < key) {
            //比关键字小则关键字在右区域
            return recursionBinarySearch(arr, key, middle + 1, high);
        } else {
            return middle;
        }
    }

    /**
     * 不使用递归的二分查找
     * @param arr
     * @param key
     * @return 关键字位置
     */
    public static int commonBinarySearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length - 1;
        if (key < arr[low] || key > arr[high] || low > high) {
            return -1;
        }
        while (low <= high) {
            int middle = (low + high) >> 2;
            if (arr[middle] > key) {
                //比关键字大则关键字在左区域
                high = middle - 1;
            } else if (arr[middle] < key) {
                //比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }



}
